package d1_midterm_examination.demo06;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * 1、设计一个Node泛型类，用于代表链表的结点。每个结点包含（数据data，和下一个结点的地址值next） 3
 * 2、开发一个类叫MyLinkedList，提供一个add方法可以让用户添加链表的结点，直到用户输入exit，则返回链表（返回链表实际上是返回链表的头结点） 5
 * 3、提供一个reverse方法，接收头指针 head 和两个整数 left 和 right ，其中 left <= right，按上面的要求进行反转。反转后，返回新的链表 9
 * 4、提供一个forEach方法，接收新链表，并对其进行遍历输出。 5
 */
public class MyLinkedList<E> {

    //4、定义一个变量记住链表的元素个数
    private int size;

    /*
    1、定义一个静态内部类,作为链表的节点
     */
    public static class Node<E> {
        //1.定义每个节点的数据区data
        E data;
        //2.定义下一个节点的指针
        Node<E> next;
        //3.提供相应的构造器

        public Node(E data, Node<E> next) {
            this.data = data;
            this.next = next;
        }
    }

    //思路: 就是用一个集合,记录开始翻转的开始节点到结束节点,的数据,然后倒着遍历, 之后注入的链表的相应位置即可
    //4、提供一个reverse方法,接受头指正head 和两个整数 left heright , 其中left <= fight , 按照上面要求进行反转。反转之后返回新链表
    public Node<E> reverse(Node<E> head, int left, int right) {
        //1.还是做极端判断(就是不翻转的情况)
        //其实这个是不用写|| right < 1
        if (head == null || head.next == null || left > right || left < 1 || left > size || right > size) {
            //直接结束方法,
            return head;
        }
        //2.定义一个节点用于记录要反转的开始节点
        Node<E> start = null;
        //4.再创建一个节点,暂存头结点
        Node<E> first = head;
        //5.再定义一个变量用于记录位置
        int index = 1;
        //7.创建一个集合,用于存储开始的反转节点到反转结束节点的数据
        List<E> reverseData = new ArrayList<>();
        //3.开循环
        while (true) {
            first = first.next;
            index++;
            //6.看当前节点是不是要反转的节点
            if (index == left) {
                //8.开始记录反转开始节点
                start = first;
            }
            //9.开始存数据
            if (index >= left && index <= right) {
                reverseData.add(first.data);
            }
            if (index == right) {
                //10.开始循环反转数据
                for (int i = reverseData.size() -1; i >= 0; i--) {
                    start.data = reverseData.get(i);
                    start = start.next;
                }
                break;
            }

        }




        return head;
    }

    //老师的写法
    // 1 2 3 4 5 6    left = 2   right = 5
    public Node<E> rev1erse(Node<E> head, int left, int right){
        if(head == null || left < 1 || left > size || right < 1 || right > size
                || left == right || left > right) {
            return head;
        }

        // 1、找出左节点的起始地址。
        // 2、从左边遍历到右节点，然后把数据先存入集合。
        Node<E> first = head;
        Node<E> mark = null;
        List<E> data = new ArrayList<>();
        int index = 0;
        while (head != null) {
            index++;
            if(index == left) {
                mark = head; // 左节点位置找到了。
            }

            if(index >= left && index <= right) {
                data.add(head.data);
            }

            if(index == right) break;

            head = head.next;
        }

        // 2、倒序遍历集合。
        for (int i = data.size() - 1; i >= 0; i--) {
            E e = data.get(i);
            mark.data = e;
            mark = mark.next;
        }

        return first;
    }

    //3、提供一个forEach方法,接受新链表, 并对其进行遍历输出
    public void forEach(Node<E> head) {
        //1.首先做极端判断
        if (head == null) {
            System.out.println(head);
            return; //当链表不存在的时候,直接结束方法
        }
        //3.首先打印头节点的数据
        System.out.print(head.data + " ");
        //2.直接从head开始一个一个找
        //开循化
        while (head.next != null) {
            //4.打印头结点下一个节点的数据, 并让头节点往下走
            head = head.next;
            System.out.print(head.data + " ");
        }
    }

    //2、提供一个add方法可以让用户添加链表的节点,直到用户输出exit, 返回头结点
    public Node<E> add() {
        //1.首先创建头节点
        Node<E> head = null;
        //4.创建一个扫描器-->用于接受用户输出的数据
        Scanner sc = new Scanner(System.in);
        //8.要反复进行输出, 所以要套循环,等带用户输入exit
        while (true) {
            //5.提示用户输出数据
            System.out.println("请您输入要存储的数据");
            //6.接收用户输出的数据
            String data = sc.next();
            //9.做判断,看是否是退出命令
            if ("exit".equals(data)) {
                break;
            }
            //2.判断是不是第一次添加数据
            if (head == null) {
                //3.是第一次添加节点,创建一个新节点,将地址复制给头节点
                head = new Node<>((E) data, null);
                //添加一次数据,size就进行++
                ++size;
            } else {
                //9.头结点不可动,不然链表就不是链表了
                Node<E> temp = head;
                //7.不是第一添加数据,开始从头节点添加数据
                //开循环
                while (temp.next != null) {
                    temp = temp.next;
                }
                //8.到这里就证明,是temp是最后一个节点了-->开始添加数据
                temp.next = new Node<>((E) data, null);//注意这里要复制给temp的指针域

                //这里也需要进行++
                ++size;
            }
        }
        return head;
    }
}
